\chapter{研究方法}
\label{cha:algorithm}

\section{问题引入}
在原论文的算法中，作者为了达到可观的准确率，其模型采用了 6 层 decoder，近百万张图片作为训练集训练了近 280 个epoch。为了训练模型，作者分布式地在 32 台 80G内存 A100 显卡上进行训练，此类显卡单张造价可达 6w，需要极高的训练成本。以单张 24G 内存的 RTX3080 显卡为例，其内存仅能支撑 2 层 decoder 的缩减规模的模型进行训练，依照原作者方式训练全部数据集预计用时也将高达 280 天，这是非常不切实际的。为了使模型更具有普适性，需要探索性能更优异的方式。为此，我们考虑能否使用更少的网络层数，更轻量的数据集来达到更好的训练效果。我们从小规模训练着手，观察其预测行为并探索改进预测效果的方法。

​	在实际训练中，如图\ref{fig:small}我们发现小规模的模型已经能够初步预测出单词雏形，对大部分不受场景光线、遮挡干扰的单词具有较小的误差。我们聚焦此类问题，重点关注预测值与真实值的误差，分析并优化模型结果，目标瞄准更低成本模型具有高规模的训练效果。

​	通过缩减模型，我们采用较小的数据集，使用相同的设备仅需约 40 个小时达到较好的效果，下面的探讨从该小规模模型深入，通过算法改进使其识别结果逼近大规模模型训练，从而节省训练成本。
\begin{figure}[h!]%文中的Grid-LSTM模型做的语义图像分割的例子
    \centering
    \includegraphics[width=.45\textwidth,height=.25\textwidth]{image/improve/image-20231129082235236.png} 
    \includegraphics[width=.45\textwidth,height=.25\textwidth]
    {image/improve/image-20231129082414448.png}

    \caption{小规模训练预测结果}
    \label{fig:small}
\end{figure}

\section{实现方法}

\subsection{理论依据}

\begin{itemize}
\item 语义无关性
\\ \indent 在模型训练中，SPTSv2 模型首先采用卷积神经网络（CNN）提取图像特征，其通过卷积操作对图像空间进行压缩，其生成的特征向量仅提取了文本的图形特征，而不关注实际单词的语义信息，没有对预测结果的语义信息做正误区分。我们可以从单词的“形”特征上入手，重点关注单词中字母之间的关联性，以找到并修正为具有现实语义的实际单词。
\item 误差相似性
\\ \indent   通过观察分析模型预测结果，我们发现预测值与实际值在编辑距离上具有类似的模式，如有较大比例预测结果重复产生了部分字母（如图\ref{fig:repeat}）。故我们可以重点关注编辑距离，通过减小此类误差来对模型进行改进。
\end{itemize}
    

\begin{figure}[h!]%文中的Grid-LSTM模型做的语义图像分割的例子
    \centering
    \includegraphics[width=.32\textwidth,height=.2\textwidth]{image/improve/image-20231129083141259.png} 
    \includegraphics[width=.32\textwidth,height=.2\textwidth]
    {image/improve/image-20231129083152839.png}
    \includegraphics[width=.32\textwidth,height=.2\textwidth]
    {image/improve/image-20231129083157240.png}

    \caption{预测结果存在字符重复}
    \label{fig:repeat}
\end{figure}

\subsection{方法技术}
我们采用基于贝叶斯方法的英文单词校对技术。令 c 为可能的正确的单词，w 为模型预测产生错误的单词，其中 c 包含在一个选定的较大的语料库中。因此问题可以转化为 $argmax_CP(c│w)$ ，而由于 $P(c│w)=P(w│c)P(c)/P(w)$ 且 $P(w)$ 恒定，概率模型可以进一步转化为求解 $argmax(P(w│c)P(c))$。其中，各个概率的定义如下：

\begin{itemize}
\item $P(c)$ 为先验概率，代表文章中出现一个正确拼写单词 c 的概率。在实现中可以通过统计 c 在语料库中出现的频次占比来给出。
\item $P(w|c)$ 表示模型期望预测为 w，但是错误预测为 c 的概率。在实际中难以进行定量分析，针对模型预测场景，我们通过结合模型行为定性分析对其进行量化。
\item $P(c|w)$ 是后验概率，表示模式期望预测为 c，但是错误预测为 w 的概率，是我们所需要求解的结果。
\end{itemize}

因此，改进模型的重点问题是对 p(w|c) 的量化。


\subsection{ P(w|c)的量化}
（1）\textbf{编辑距离}

编辑距离是针对两个字符串的差异程度的量化量测，其计算将一个字符串变成另一个字符串的处理步数。对学符串，增、删、改、交换宇符四种方式视为一次处理，鉴于模型仅关注图形特征的特性，其不存在交换字符的错误模式，故我们关注增、删、改三种处理模式。其中图\ref{fig:distance}展示了得到编辑距离的具体例子。
\begin{figure}[h]
    \centering
    \includegraphics[width=\textwidth]{image/improve/image-20231129084619908.png}
    \caption{编辑距离}
    \label{fig:distance}
\end{figure}


（2）\textbf{数据准备} 

我们设计了计算编辑距离的算法，通过动态规划等方式计算模型预测值和实际值的编辑距离和处理方式，我们可以对训练集的所有预测结果与标签进行对比，统计各种复合处理方式的数量并计算其概率。 
对预测值和实际值的对比解析要求得出最少的处理步数和处理操作。在得到变换模式前，我们首先需要得到两个字符串最相近的部分，即实际值与预测值的最长相同子字符串，其余不同部分字符即为从实际值到预测值的应处理字符。得到相同子字符串后我们需要解析如何通过三种变换（增、删、改）将实际值变换到预测值，即模型行为的分析。实际上，在最后的修正部分所做的变换是该变换的逆变换，故我们可以直接计算预测值到实际值的变换模式并统计其概率。
​由此，我们可以将该问题分解为两个部分：获取最长相同子串匹配和解析变换模式。

\textbf{a. 获取最长相同子串}

对于该部分，我们可以采用动态规划的方法。假设预测值为长度为 $l_1$ 的字符串 $str_1$，实际值为长度 $l_2$ 的字符串 $str_2$，则我们可以构建大小为 $(l_1+1) * (l_2+1)$ 的矩阵，对位置为 $(i, j)$ 的元素，其定义为求解子问题 $str_1[0:i]$ 和 $str_2[0:j]$ 的最长相同子串。其中 $str[i:j]$ 表示字符串 $str$ 从第 i 位到第 j-1 位的子字符串。

对每个子问题进行分析，可以发现，当 $str_1[i-1]$ 对应的字符与 $str_2[j-1]$ 相同时，该字符可以添加到最长相同子串当中，此时最长相同子串为 max{子问题 $dp[i-1, j-1]$ 所得子串加上该相同字符, 子问题$dp[i-1, j]$所得子串，子问题${dp[i, j-1]}$ 所得子串}。当对应字符不相同时，最长相同子串与子问题 $dp[i-1, j]$ 、 $dp[i, j-1]$ 、$dp[i-1, j-1]$ 中的较大者相同。

从动态规划矩阵 $dp$ 的 0，0 位置开始解算，最终 $l_1$, $l_2$ 位置所对应的结果即为最长相同子串。图\ref{fig:longgest_string}为子串匹配的举例说明。
    \begin{figure}[h]
        \centering
        \includegraphics[width=\textwidth]{image/improve/Snipaste_2023-12-04_22-40-15.png}
        \caption{最长相同子串及匹配下标}
        \label{fig:longgest_string}
    \end{figure}

\textbf{b. 解析变换模式}

在获取最长匹配子串的过程中，我们记录下该过程对应的字符下标映射，根据该下标映射我们可以解析出每一步变换的具体操作，进而得到编辑距离的编辑模式。我们计算每一位匹配字符的下标间隔，当下标间隔相同时，其间的字符可以通过改操作来变换，使得 $change = change + dx(或dy) - 1$。当下标间隔不同时，对于 dx、dy 中较小量可以通过改操作变换，对于盈余部分可以通过增（或删）操作进行变换。具体实现如算法\ref{algo:process}所示。

\begin{algorithm}[h]
    \KwIn{目标文本$dst$和源文本$src$}
    % \Comment{$\#$获取最长相同子字符串} \\
      $\text{dp} \leftarrow $ 初始化为大小是 $(len(dst) + 1) \times (len(src) + 1)$的矩阵 \\
    \ForEach{$i=1$ \emph{\KwTo} $len(dst)+1$}{
        \ForEach{$j=1$ \emph{\KwTo} $len(src)+1$}{
            \If{$\text{dst[i-1] == src[j-1]}$}{
                  $dp[i][j][0] \leftarrow dp[i-1][j-1][0] + 1$ 
                  $dp[i][j][1] \leftarrow dp[i-1][j-1][1] + [[i-1, j-1]]$ 
            } 
            \Else{
                  $dp[i][j] \leftarrow max(dp[i-1][j], dp[i][j-1], key=lambda c: c[0])$ 
            }   
            % \EndIf
        }
    }  
    $\text{path} \leftarrow$ $dp$矩阵最终求的的最长相同字符串的模式结果 \\
    $\text{last} \leftarrow$ $[-1,-1]$\\
    为path添加 $[len(dst), len(src)]$ \\
    对三种模式进行初始化为：$add,delete,change = 0,0,0$\\
    \ForEach{在path里的坐标对pair}{
          {$dx \leftarrow$ $pair[0] - last[0]$} \\
          {$dy \leftarrow$ $pair[1] - last[1]$} \\
        \If{$\text{dx == dy}$}{
              $change  \leftarrow change + dx - 1$ 
        } 
        \If{$\text{dx > dy}$}{
              $change  \leftarrow change +  min(dx, dy) - 1$ 
              $delete  \leftarrow delete + dx - dy$ 
        }   
        \Else{
              $change  \leftarrow change +  min(dx, dy) - 1$ 
              $add  \leftarrow add + dy - dx$ 
        }
        % \EndIf
        $last \leftarrow$ $pair$ \\
    }
    \KwOut{$add,delete,change$}
    \caption{解析编辑模式算法}
    \label{algo:process}
\end{algorithm}  

（3）\textbf{量化概率}

编辑距离是针对两个字符串的差异程度的量化量测，其计算将一个字符串变成另一个字符串的处理步数。对字符串，增、删、改、交换字符四种方式视为一次处理，鉴于模型仅关注图形特征的特性，其不存在交换字符的错误模式，故我们关注增、删、改三种处理模式，对预测单词依次进行三种变换生成所有可能的结果。

​鉴于复杂性我们实现了最多2步的变换分析，当输入一个错误预测的单词后，我们得到所有其经过最多两步变换的单词 c 。 


根据生成的单词，计算其变换模式 process，则每个新单词对应的似然概率 $P(w|c)= P_{process}$ 。
\begin{figure}[h]
    \centering
    \includegraphics[width=\textwidth]{image/improve/image-20231129084909140.png}
    \caption{处理模式概率映射}
    \label{fig:process}
\end{figure}

总而言之，计算似然概率 $P(w|c)$ 大致分为处理过程和解析过程：

在处理过程中，首先对小规模模型预测的行为进行分析，计算预测值和实际值的编辑距离，并通过解析得到其编辑模式（a,d,c）。在得到所有预测单词的编辑模式后即可统计各种模式出现的频次，进而近似得到模型预测结果误差模式的概率，形成概率向量 $P_{process}$ 。

在解析过程中，对产生的预测结果，我们计算他的所有编辑距离为 2 的单词，同时记录其编辑模式（a,d,c），进而映射到概率向量中找到该模式的生成概率，将其作为  $P(w|c)$。

\subsection{分类器}

通过上述计算，我们已经能够获取 $P(c)$ 和 $P(w|c)$。通过计算 $P(c)*P(w|c)$ 可以对结果进行分类，筛选出正确的预测结果，即 $argmax_c(P(c)*P(w|c))$。具体实现如算法\ref{algo:bayes}所示。

\begin{algorithm}[h]
    \KwIn{预测单词$word$，字典$nwords$，模式概率表$pwc$}
    \If{$word$在字典$nwords$里}{
          \KwOut{原单词$word$}
    } 
      $\text{c} \leftarrow $ 距$word$编辑距离为2以内的所有单词\\
      $\text{c} \leftarrow $ $c$中先验概率不为0的单词\\
    \If{$len(c)=0$}{
          \KwOut{原单词$word$} 
    } 
    \ForEach{在c中的元组ci}{
          {$pair \leftarrow$ $(ci[0], nwords[ci[0]] * pwc[ci[1]])$} \\ 
          {将pair存储到列表pcw中} \\
        
        $last \leftarrow$ $pair$ \\
    }
    $\text{res} \leftarrow $ $max(pcw, key=lambda i: i[1])$ \\
    \KwOut{$add,delete,change$}
    \caption{贝叶斯分类器}
    \label{algo:bayes}
\end{algorithm}  


\subsection{复杂性分析}

设n为字符串长度，m为步长。则增操作复杂度为 n+1, 删操作和改操作复杂度为 n。在生成所有可能的实际单词过程中，增、删、改得到的单词个数如下：
\begin{align}
    a(n)&=26(n+1)\\
    d(n)&=n\\
    c(n)&=26n
\end{align}

故在生成编辑距离为 1 的所有单词时算法的复杂度为:
\begin{align}
    时间复杂度：f_1(n)&=[a(n)+d(n)+c(n)]n=53n^2+26n\\
    空间复杂度：g_1(n)&=a(n){\times}(n+1)+d(n){\times}(n-1)+c(n){\times}n=53n^2+51n+26
\end{align}

在生成编辑距离为 2 的所有单词时算法的复杂度为:
\begin{align}
	\begin{split}
		时间复杂度：f_2(n)&=a(n)f_1(n+1)+d(n)f_1(n-1)+c(n)f_1(n)\\
		&=2809n^3+5406n^2+5513n+2054
	\end{split} \\
	\begin{split}
		空间复杂度：g_2(n)&=a(n)g_1(n+1)+d(n)g_1(n-1)+c(n)g_1(n)\\
		&=2809n^3+6731n^2+8166n+3380
	\end{split}
\end{align}

在生成编辑距离为 3 的所有单词时算法的复杂度为:
\begin{align}
	\begin{split}
		时间复杂度：f_3(n)&=a(n)a(n+1)f_1(n+2)+a(n)d(n+1)f_1(n)+a(n)c(n+1)f_1(n+1)\\
		&\ \ \ \ \ d(n)d(n-1)f_1(n-2)+d(n)c(n-1)f_1(n-1)+c^2(n)f_1(n) \\
		&=110293n^4+446571n^3+1006338n^2+1053022n+410332
	\end{split} \\ 
	\begin{split}
		空间复杂度：g_3(n)&=a(n)a(n+1)f_1(n+2)+a(n)d(n+1)f_1(n)+a(n)c(n+1)f_1(n+1)\\
		&\ \ \ \ \ d(n)d(n-1)f_1(n-2)+d(n)c(n-1)f_1(n-1)+c^2(n)f_1(n) \\
		&=110293n^4+446571n^3+1006338n^2+1053022n+410332
	\end{split}
\end{align}

事实上，考虑实际增、删、改操作的具体指令以及复杂的内存管理方式，复杂度将再上升数个量级。根据计算，以每个单词 10 个字符为例，两步操作的时间复杂度将到达 $2.82 \times 10^6$，根据测试实际耗时约 1.62 秒。 而三步操作复杂度将达到 $1.6 \times 10^9$，实际耗时根据计算需要至少约 8 小时，无法在有限的时间内实现实时转化。

